import sun.security.util.Length;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by losor on 2017/3/8.
 */
public class _122_BestTimeToBuyAndSellStockII {
    public static void main(String[] args) {
        int[] a = new int[]{1,2};
        _122_BestTimeToBuyAndSellStockII s = new _122_BestTimeToBuyAndSellStockII();
        System.out.println(s.maxProfit(a));
    }
    public int maxProfit(int[] prices) {
        if (prices.length == 0 || prices.length == 1){
            return 0;
        }

        int index = 0;
        int[] b = new int[prices.length];
        b[0] = prices[0];
        b[prices.length-1] = prices[prices.length-1];
        for (int i = 1; i < prices.length-1; i++) {
            if (!(prices[i-1] >= prices[i] && prices[i] >= prices[i+1])){
                index++;
                b[index] = prices[i];
            }
        }
        index++;
        b[index] = prices[prices.length-1];
        int[] c = new int[index+1];
        for (int i= 0; i < index+1; i++) {
            c[i] = b[i];
        }
        int[][] a = new  int[c.length][c.length];
        a[0][0] =  0;
        for (int j = 1; j < c.length; j++) {
                if (c[j] - c[0] > 0) {
                    a[0][j] =  c[j] - c[0];
                } else {
                    a[0][j] = 0;
                }
        }
        for (int i = 1; i < c.length; i++) {
            int root = a[i][i] = a[i-1][i];
            for (int j = i+1; j < c.length; j++) {
                int sum = c[j] - c[i];
                        if ( sum > 0 ){
                            a[i][j] = root + sum;
                        }
                        else{
                            a[i][j] = root;
                        }
                        a[i][j] = a[i-1][j]>a[i][j]?a[i-1][j]:a[i][j];
                    }
                }
        return a[c.length - 1][c.length-1];
    }

    //所以，其实直接后面一个数比前面一个数大的话，就加上，否则的话就不加
    public int maxProfitsimple(int[] prices) {
        int total = 0;
        for (int i=0; i< prices.length-1; i++) {
            if (prices[i+1]>prices[i]) total += prices[i+1]-prices[i];
        }

        return total;
    }
}
